\section{附录 \thesection: 矩阵与图}\label{00F}

\begin{frame}{谱}
 复方阵 $A$ 的所有特征值构成的集合称为 $A$ 的\emph{谱} (spectrum)，记作 $\sigma(A)$. 
  设 $\lambda_1, \cdots, \lambda_r$ 为 $A$ 的所有不同特征值。那么
  \[
    \sigma(A)=\{\lambda_1, \cdots, \lambda_r\}.
  \]
$A$ 的特征值的模的最大值称为
$A$ 的\emph{谱半径} (spectral radius)，记作 $\rho(A)$. 即
\[
  \rho(A)=\max\{|\lambda_1|, \cdots, |\lambda_r|\}.
\]

~

有些地方对谱的定义要求把重数也考虑进来，此时 $A$ 的谱指
\[
  \sigma(A)=\{\lambda_1^{(m_1)}, \cdots, \lambda_r^{(m_r)}\},
\]
其中 $m_i$ 为 $\lambda_i$ 的重数（重数 $1$ 通常忽略不写）。
\end{frame}

\begin{frame}
我们有
\begin{enumerate}
  \item $\sigma(A^{\rT})=\sigma(A)$.
  \item 若 $A=\begin{pmatrix}
          A_1 & A_3\\ 0 & A_2
        \end{pmatrix}$ 是准上三角阵，则 $\sigma(A)=\sigma(A_1)\cup \sigma(A_2)$.
  \item 若 $A$ 可逆，则 $\sigma(A^{-1})=\{\lambda_1^{-1}, \cdots, \lambda_r^{-1}\}$.
  \item 对正整数$k$, $\sigma(A^k)=\{\lambda_1^k, \cdots, \lambda_r^k\}$. 一般地，对多项式$f(\lambda) \in \CC[\lambda]$, 
    $\sigma(f(A))=\{f(\lambda_1),\cdots,f(\lambda_r)\}$.
    特别地，
    $\sigma(dE -A)=\{d-\lambda_0\mid \lambda_0\in \sigma(A)\}$.
  \item 若 $A, B$ 相似，则 $\sigma(A)=\sigma(B)$.
\end{enumerate}

即使把重数考虑进来，上面列的五条事实也是对的（加上显然的重数即可，除了第 (2) 条中合并 $A_1, A_2$ 的特征值时要把同一个特征值的重数加起来）。


\end{frame}



\begin{frame}{矩阵及其特征值在图论中的应用}
  \begin{wrapfigure}{r}{.25\textwidth}
    \centering
    \begin{tikzpicture}
      [
        scale=.8,thick,inner sep=1mm,
        vertex/.style={circle,draw=cyan!50,fill=cyan!20,thick}
      ]
      \node (v1) at (0,2) [vertex] {$v_1$};
      \node (v2) at (2,1) [vertex] {$v_2$};
      \node (v3) at (0,0) [vertex] {$v_3$};
      \draw[->-=.53,pink] (v3) -- (v1);
      \draw[->-=.53,pink] (v3) to[bend right=15] (v2);     
      \draw[->-=.53,pink] (v2) to[bend right=15] (v3);
      \draw[->-=.53,pink] (v2) to[bend left=15] (v1);     
      \draw[->-=.53,pink] (v1) to[bend left=15] (v2);
    \end{tikzpicture}
    \caption*{图 3}
  \end{wrapfigure}
  观察有向图图 3. $v_{1}, v_{2}, v_{3}$ 是三个顶点，例如代表三个旅游景点。
  $\overrightarrow{v_{1} v_{2}}, \overrightarrow{v_{2} v_{1}}, \overrightarrow{v_{3} v_{1}}, \overrightarrow{v_{2} v_{3}}, \overrightarrow{v_{3} v_{2}}$ 
  是它的边(有向边), 代表景点之间有道路相通，例如 $v_{2}, v_{3}$ 之间有双向道路，而 $v_{1}, v_{3}$ 之间只有 $\overrightarrow{v_{3} v_{1}}$ 单行通道。

  这个图
  \footnote{关于有向图，我们约定任一顶点到另一顶点至多一条有向边，任一顶点到自己没有有向边。}
  的顶点和有向边的状况可用一个 $3 \times 3$ 矩阵 $A=(a_{i j})_{3 \times 3}$ 来描述，
  若 $v_{i}, v_{j}$ 之间有有向边 $\overrightarrow{v_{i} v_{j}}$, 则令 $a_{i j}=1$,
  否则令 $a_{i j}=0$.
  这个矩阵 $ A$ 称为有向图图 3 的\emph{邻接矩阵} (adjacent matrix)。易知
\[
A=\left(\begin{array}{lll}
0 & 1 & 0 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{array}\right).
\]

若有几条边， 依次地前一边的终点与它后面的边的起点一致， 把它依同一顺序连接起来称为一条（有向）\emph{链} (walk)。
例 $\overrightarrow{v_{1} v_{2}}, \overrightarrow{v_2v_{3}}$;
$\overrightarrow{v_3v_{1}}, \overrightarrow{v_1v_{2}}, \overrightarrow{v_{2}v_{3}}$ 分别是长为 $2$ 和 $3$ 的链。 
第二条路中的起点与终点一致， 称为\emph{闭链} (closed walk)， 是一条往返旅行线路。 它与 $\overrightarrow{v_{1} v_{2}}$, $\overrightarrow{v_{2} v_{3}}, \overrightarrow{v_{3} v_{1}}$ 在几何上是同一个圈图， 但起、终点不同， 是不同的闭链。 $\overrightarrow{v_{1} v_{2}}$ 单独一条有向边， 是长为 $1$ 的路。

为了记号的简便，我们用有向图的链经过的顶点序列来记该链：$(v_1,\cdots,v_r)$, 
其中 $(v_{i}, v_{i+1})$ 为边，对 $i=1,\cdots,r-1$; 其长度为 $r-1$.
如链$\overrightarrow{v_{1} v_{2}}, \overrightarrow{v_2v_{3}}$记作$(v_1, v_2, v_3)$.
所有顶点 $v_1,\cdots,v_r$ 互异的链称为（有向）\emph{路（径）} (path)。
如$(v_1, v_2, v_3)$就是一条路径。
\end{frame}

\begin{frame}
  从 $v_{i}$ 到 $v_{j}$ 的长为 $k$ 的链 (可以 $i=j$, 这时是闭链) 有几条? 
  我们有以下
\begin{proposition}
设一个有向图有 $n$ 个顶点 $v_{1}, v_{2}, \cdots, v_{n}$. 它的邻接矩阵 $ A=\left(a_{i j}\right)_{n \times n}$. 令 $ A^{k}=$ $\left(b_{i j}\right)_{n \times n}$, 则从 $v_{i}$ 到 $v_{j}$ 的长为 $k$ 的链的数目是 $b_{i j}$.
\end{proposition}
\begin{proof}
  对 $k$ 作归纳法。 $k=1$ 时命题显然成立。 令$k \geqslant 2$, 设 $k-1$ 时命题已成立。
%令 $ A^{k-1}=\left(c_{i j}\right)_{n \times n}$, 由归纳假设 $c_{i j}$ 是从 $v_{i}$ 到 $v_{l}$ 的长为 $k-1$ 的链的数目。 由 $v_{i}$ 到 $v_{j}$ 的任一长为 $k$ 的链必为 $v_{i}$ 到某 $v_{l}$ 的长为 $k-1$ 的链接上长为 $1$ 的链 $\overrightarrow{v_{l} v_{j}}$. 以这样方式经过 $v_{l}$ 的长为 $k$ 的链的数目为 $c_{i l} a_{1 j}$. 如从 $v_{i}$ 到 $v_{j}$ 无上述方式经过 $v_{l}$ 的长为 $k$ 的链。 有两种可能： 一种是无 $v_{i}$ 到 $v_{i}$ 的 $k-1$ 长度的链， 有 $c_{i l}=0$, 另一种可能没有边 $\overrightarrow{v_{i} v_{j}}$, 则 $a_{l j}=0$. 从 $v_{i}$ 到 $v_{j}$ 按上述方经过这个 $v_{l}$ 的长为 $k$ 的链的数目为 $0$ 也等于 $c_{i l} a_{i j}$. 由于 $v_{l}$ 可任选 $v_{1}$, $v_{2}, \cdots, v_{n}$, 故 $v_{i}$ 到 $v_{j}$ 的长为 $k$ 的链的总数为
%\[
%  \sum_{i=1}^{n} c_{i l} a_{l j}=b_{i j}.
%\]
%归纳法完成。 
  令$A^k=(a_{ij}^{(k)})$. 我们有
  \[\tag{$*$}
    a_{ij}^{(k)} = \sum_{l=1}^n a_{il}^{(k-1)} a_{lj}.
  \]
  我们要证明等号右边正是$v_i$到$v_j$的长为$k$的链的数目。
  求和项$a_{il}^{(k-1)} a_{lj}\neq 0$相当于存在一条长度$k$的链$(v_i,\cdots,v_l, v_j)$. 
  我们来数下这样的链的数目。
  按照归纳假设，形如$(v_i,\cdots,v_l)$的长度为$k-1$的链的数目为$a_{il}^{(k-1)}$; 因此形如$(v_i,\cdots,v_l,v_j)$的长度为$k$的链的数目为$a_{il}^{(k-1)} a_{lj}$. 
  对所有可能的$v_l$, 相应的数目正好是 ($*$) 右边相应的求和项。
  由此，($*$) 式给出的就是$v_i$到$v_j$的长度$k$的链的数目。
\end{proof}
\end{frame}

\begin{frame}

现在可进一步计算出有向图中所有长为 $k$ 的闭链的数目。由上面的命题知， 以任一点 $v_{i}$ 为起、终点的长为 $k$ 的闭链的数目为 $b_{i i}$, 故有向图中长为 $k$ 的闭链的数目为 $\sum_{i=1}^{n} b_{i i}=\operatorname{tr}  A^{k}$.

设有向图的邻接矩阵为 $A$, 它的 $n$ 个复特征值为 $\lambda_{1}, \lambda_{2}, \cdots, \lambda_{n}$. 那么 $ A^{k}$ 的$n$个复特征值为 $\lambda_{1}^{k}, \lambda_{2}^{k}, \cdots, \lambda_{n}^{k}$. 进而 有向图中长为 $k$ 的闭链的数目为
\[
  \operatorname{tr} A^{k}=\sum_{i=1}^{n} b_{i i}=\sum_{i=1}^{n} \lambda_{i}^{k}.
\]

本例题开头的有向图图 3 的邻接矩阵 $ A$ 的特征多项式为
\[
|\lambda E-A|=\left|\begin{array}{ccc}
\lambda & -1 & 0 \\
-1 & \lambda & -1 \\
-1 & -1 & \lambda
\end{array}\right|=(\lambda+1)\left(\lambda^{2}-\lambda-1\right)
\]
特征值为 $-1, \frac{1+\sqrt{5}}{2}, \frac{1-\sqrt{5}}{2}$. 图 3 中长为 $k$ 的闭链的数目为 $(-1)^{k}+\left(\frac{1+\sqrt{5}}{2}\right)^{k}+\left(\frac{1-\sqrt{5}}{2}\right)^{k}$.

\end{frame}

\begin{frame}{Perron-Frobenius定理介绍}

非负矩阵在实际中应用甚广。
有关非负方阵的特征值、特征向量的的事实中最重要的当属 Perron-Frobenius 定理。
此定理有很多应用（如在经济学、人口模型、图论、Markov链等领域中）。
关于正矩阵、非负矩阵、本原矩阵的一般理论可参见~\cite[第 8 章]{HJ13}.
Perron-Frobenius定理在Markov链中的应用参见 \cite[第 9 章]{Gen17}
（比如Google 的 PageRank 算法的可行性就是用了 Perron-Frobenius 定理来得到页面排行过程这个Markov链的收敛性）；
在图论中的应用参见 \cite[第 8 章]{GR01}（可以看到 Perron-Frobenius 定理可用于特征分析来刻画图的性质）。


%  \begin{definition}
%  每行每列都恰好只有一个 $1$ 而其余元素都是 $0$ 的方阵称为\emph{置换矩阵}。
%  \end{definition}
%
%  若 $n>1$, $n$ 阶矩阵 $P$ 是置换矩阵也相当于 $P$ 可由单位矩阵做若干次交换两行这样的初等变换得到，
%  亦相当于 $P$ 可写为若干个对换矩阵的乘积，这里对换矩阵指实现交换两行（或列）这样的初等变换的初等矩阵%
%  \footnote{下次在上学期介绍置换的概念就可以说得很清楚！这次只能临时补下，置换矩阵不是这里的重点。}。
%  置换矩阵 $P$ 满足 $P^{\rT}=P^{-1}$. 

\begin{definition}
  方阵 $A$ 称为\emph{可约} (reducible)，若存在置换矩阵 $P$ 使得 $P^{\rT}AP=\begin{pmatrix}
        B & D \\ 0 & C
      \end{pmatrix}$, 其中 $B, C$ 是方阵。否则 $A$ 称为\emph{不可约} (irreducible)。
\end{definition}
这样可约相当于可以经对称的置换（一系列形如 $c_i\leftrightarrow c_j, r_i\leftrightarrow r_j$ 这样的对称的初等变换）变成形如
$\begin{pmatrix}
  B & D \\ 0 & C
\end{pmatrix}$, 反之则是不可约。
如 $\begin{pmatrix}
  0 & 1 \\ 2 & 0
\end{pmatrix}$ 就是个不可约矩阵。
\end{frame}

\begin{frame}


\begin{definition}
  $A=(a_{ij})\in \bR^{m\times n}$ 称为\emph{非负} (nonnegative)，若所有的元素 $a_{ij}\geqslant 0$, 通常记作 $A\geqslant 0$;
  $A$ 称为\emph{正} (positive)，若所有元素 $a_{ij}>0$, 通常记作 $A>0$. 
  方阵 $A$ 称为\emph{本原} (primitive)，若对某个正整数 $k$ 有 $A^k>0$. 
\end{definition}
容易发现，对非负方阵，我们有如下的蕴含关系：正 $\Rightarrow$ 本原 $\Rightarrow$ 不可约。
正方阵有很好的性质，特别是Perron定理。
Perron定理中有一条说正方阵的谱半径是该方阵的单特征值，还有一条叙述了一个重要的渐进性质（参见 \cite[定理 8.2.8]{HJ13}）。
不过实际中的矩阵可能只满足非负性。
非负性不是一个很强的性质，Perron定理所叙述的性质对一般的非负方阵不成立。
要获得Perron定理给出的正面性质，我们所需的条件正是不可约性。
对于不可约的非负矩阵，Perron定理的推广版本是Perron-Frobenius定理。
不过要把渐进性质这条包含进来（在某些应用中，如Markov链的理论中，我们还需要渐进性质），
不可约的假定还不够，我们需要本原这个概念。

\end{frame}

\begin{frame}{非负矩阵的不可约性的刻画}
  每个 $n\times n$ 矩阵 $A=(a_{ij})$ 可关联一个有向图 $\Gamma_A=(V_A, E_A)$，其中顶点集 $V_A=\{1,\cdots,n\}$,
  边集 $E_A=\{(i,j)\mid a_{ij}\neq 0\}$.
  $\Gamma_A$ 称为 \emph{$A$ 的有向图} (the digraph of $A$)。例如矩阵
  $
    A=\begin{pmatrix}
    0 & 2 & 0 \\
    0 & 0 & 4\\
    7 & 3 & 0
\end{pmatrix}$
的有向图为
\[
  \begin{tikzpicture}
    [
      scale=0.8,thick,
      vertex/.style={circle,draw=red!50,fill=red!20,thick}
    ]
    \node (v1) at (0,2) [vertex] {$1$};
    \node (v2) at (2,1) [vertex] {$2$};
    \node (v3) at (0,0) [vertex] {$3$};
    \draw[->-=.53,blue!50] (v3) -- (v1);
    \draw[->-=.53,blue!50] (v3) to[bend left=15] (v2);     
    \draw[->-=.53,blue!50] (v2) to[bend left=15] (v3);
    \draw[->-=.53,blue!50] (v1) -- (v2);     
  \end{tikzpicture}
\]

\begin{theorem}
  对非负的方阵 $A\in \bR^{n\times n}$, 下列条件等价：
\begin{enumerate}
  \item $A$ 不可约。
  \item $A$ 的有向图是强连通的，即 $A$ 任意两个不同的顶点可由一条有向路径连接。
  \item 对任意的一对指标 $(i,j)$ (其中 $1\leqslant i\neq j\leqslant n$), 存在正整数 $m$ 使得 $(A^{m})_{ij}\neq 0$.
  \item $(E+A)^{n-1}>0$.
  \end{enumerate}
\end{theorem}

\end{frame}

\begin{frame}

\begin{proof}

    先证条件 (1) 和 条件 (2) 的等价性。假设 $A$ 的有向图 $\Gamma_A$ 不是强连通的。
  由对 $\Gamma_A$ 的假设知存在顶点 $w\neq j\in V_A$, 使得不存在从 $w$ 到 $j$ 的有向路径。
  令 $V'\subset V_A$ 为存在一条从 $v$ 到顶点 $j$ 的有向路径的那些顶点 $v$ 的集合。
  定义集合 $V_1 = V'\cup\{ j\}$ 和 $V_2 = V_A \setminus V_1$.
  由这两个集合的构造可知，不存在一条从 $V_2$ 中的一顶点 $w$ 到 $V_1$ 中的一顶点 $v$ 的路径；
  否则，可以将从 $w$ 到 $v$ 的路径与从 $v$ 到 $j$ 的路径连接起来，得到一条从 $w$ 到 $j$ 的路径，这与假设矛盾，因为 $V_2 \cap V_1 = \emptyset$.
  基于对 $w$ 和 $j$ 的假设，我们有 $j \in V_1\neq \emptyset$, $w \in V_2\neq \emptyset$.
  经过适当的顶点重编号，我们可以不失一般性地假定 $V_1 = \{1, \cdots, r\}$, $V_2 = \{r + 1, \cdots , N\}$，其中 $1 \leqslant r \leqslant N − 1$.
  因此，存在一个置换矩阵 $P$，使得
  \[
    P^{\rT}AP=\begin{pmatrix}
      B& C\\ 0 & D
    \end{pmatrix}.
\]
由此可得，矩阵 $A$ 是可约的。
反过来，如果矩阵 $A$ 是可约的，则从集合 $V_2 = \{r + 1, \cdots, N\}$ 到集合 $V_1 = \{1, \cdots, r\}$ 不存在任何路径。因此，该图不是强连通的。

~

再证条件 (2) 和条件 (3) 的等价性。令 $A^m=(a_{ij}^{(m)})$. 对正整数 $m$，和
\[
  a^{(m)}_{ij} = \sum_{k_1,\cdots,k_{m-1}} a_{ik_1}a_{k_1k_2}\cdots a_{k_{m-1}j} = 0
\]
当且仅当每个和项均为零，这反过来等价于不存在从 $i$ 到 $j$ 的长度为 $m$ 的链这一性质。因此，条件 (2) 与条件 (3) 等价。

\end{proof}
\end{frame}

\begin{frame}
  \begin{proof}[续]
    最后证条件 (1) 和条件 (4) 的等价性。
    先设 $(E+A)^{n-1}>0$. 若 $A$ 可约，则存在置换矩阵 $P$ 使得
    \[
      P^{\rT}AP=\begin{pmatrix}
        B & C \\ 0 &D
      \end{pmatrix},
    \]
    这样
    \[
      P^{\rT}(E+A)^{n-1} P = \left( P^{\rT} (E+A) P \right)^{n-1}=\begin{pmatrix}
        (E+B)^{n-1} & * \\ 0 &(E+D)^{n-1}
      \end{pmatrix}.
    \]
    故 $(E+A)^{n-1}$ 可约，这与 $(E+A)^{n-1}>0$ 矛盾了。
    反过来，设 $A$ 不可约。
  令 $(E+A)^{k}=(a_{ij}^{(k)})$. 那么由
    \[
      (E+A)^{n-1}=\sum_{i=0}^{n-1}\binom{n-1}{k} A^{k}
    \]
    知
    \[
      a_{ij}^{(n-1)} = \sum_{i=0}^{n-1} \binom{n-1}{k} a_{ij}^{(k)}.
    \]
    $a_{ii}^{(0)}>0$ 表明 $a_{ii}^{(n-1)}>0$.
    若 $i\neq j$, 由于 $\Gamma_A$ 强连通，存在顶点 $i$ 到顶点 $j$ 的一条有向路径，从而对某个 $1\leqslant k\leqslant n-1$ 有 $a_{ij}^{(k)} > 0$.
    这样 $a_{ij}^{(n-1)} > 0$.
    这就证明了 $(E+A)^{n-1}>0$.
  \end{proof}
\end{frame}

\begin{frame}{不可约非负方阵的Perron-Frobenius定理}
  \begin{theorem}
    如果 $A\in \bR^{n\times n}$（其中 $n\geqslant 2$）是不可约的非负矩阵，那么
    \begin{enumerate}
      \item $\rho(A)>0$. 
      \item $\rho(A)$ 是 $A$ 的单特征值（即重数为$1$的特征值）。$\rho(A)$ 称为 $A$ 的 \emph{Perron根} (Perron root)。特别地，$\rho(A)$ 的几何重数为 $1$.
      \item 存在唯一的 $X=(x_1,\cdots,x_n)^{\rT} \in \bR^{(n)}$, 使得
        $AX=\rho(A)X$ 以及 $\sum_{i=1}^n x_i=1$; 这个向量 $X$ 是正的，称为 $A$ 的\emph{右Perron向量} (right Perron vector)。
      \item 存在唯一的 $Y=(y_1,\cdots,y_n)^{\rT} \in \bR^{(n)}$, 使得
        $Y^{\rT}A=\rho(A)Y^{\rT}$ 以及 $\sum_{i=1}^n x_iy_i=1$; 这个向量 $Y$ 是正的，称为 $A$ 的\emph{左Perron向量} (left Perron vector)。
    \end{enumerate}
    如果 $A$ 还是本原的，那么我们还有
    \begin{enumerate}
        \setcounter{enumi}{4}
      \item $\lim_{m\rightarrow \infty} \left( \rho(A)^{-1}A \right)^{m} = X Y^{\rT}$, 其中 $X, Y$ 分别为 $A$ 的右、左Perron向量。
    \end{enumerate}
    如果 $A$ 还是正的，那么我们还有
    \begin{enumerate}
      \setcounter{enumi}{5}
    \item 对 $A$ 的每个满足 $\lambda\neq \rho(A)$ 的特征值 $\lambda$, 总有 $|\lambda|<\rho(A)$. 
    \end{enumerate}
  \end{theorem}
  证明参见 \cite[第 8 章]{HJ13}.
  \cite[\S8.5]{HJ13} 还证明了一些本原性的判断方法（包括一个图论的判断方法）。
\end{frame}


